﻿//15.Write a program that finds all prime numbers in the range [1...10 000 000].
//Use the sieve of Eratosthenes algorithm (find it in Wikipedia).


using System;
using System.Collections.Generic;

class SieveOfEratosthenes
{
    static void Main()
    {
        long numberN = long.Parse(Console.ReadLine());
        bool[] arr = new bool[numberN];
        int counter = 0;

        for (int i = 2; i < Math.Sqrt(numberN); i++)
        {
            if (arr[i] == false)
            {
                for (int j = i * i; j < numberN; j = j + i)
                {
                    arr[j] = true;
                }
                counter++;
                Console.WriteLine(i);
            }
        }

        for (int i = (int)Math.Sqrt(numberN) + 1; i < numberN; i++)
        {
            if (arr[i] == false)
            {
                Console.WriteLine(i);
                counter++;
            }
        }
        Console.WriteLine(counter);
    }
}
